package swardToOffer.abstractModeling;

import java.util.Arrays;

/**
 * @Author ChanZany
 * @Date 2021/5/27 9:07
 * @Version 1.0
 * <p>
 * 面试题60：n个骰子的点数
 * 题目：把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。
 * 你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。
 * n个骰子的点数和区间为[n,6n].基于排列组合的知识,可以知道n个骰子的所有点数的排列数为6^n.要解决这个问题,
 * 我们需要统计出每个点数出现的个数,然后吧每个点数出现的次数处于6^n,就能求出每个点数出现的概率.
 * 解法1:暴力求解筛子点数
 * 解法2:动态规划
 * 设输入n个骰子的解（即概率列表）为 f(n) ，其中「点数和」x的概率为f(n,x) 。
 * 假设已知n-1个骰子的解 f(n-1),此时添加一枚骰子.求n个骰子的点数和为x的概率f(n,x)
 * 由于点数和需要是x,所以前n-1个骰子和只能是x-i,其中i为第n个骰子的点数(1~6),故可以得到下面的公式
 * f(n,x) = \sum_{i \in [1,6]} f(n-1,x-i);
 * 基于此,可以得知该问题的解f(n)可以通过子问题的解f(n-1)递推出来,而输入一个骰子的解f(1)为[1/6,1/6,1/6,1/6,1/6,1/6]
 * 观察发现，以上递推公式虽然可行，但f(n−1,x−i) 中的x−i 会有越界问题。
 * 例如，若希望递推计算f(2,2) ，由于一个骰子的点数和范围为[1,6] ，
 * 因此只应求和f(1,1) ,即f(1,0) ,f(1,−1) , ... ,f(1,−4) 皆无意义。此越界问题导致代码编写的难度提升。
  f(n-1,x)仅与f(n,x+1),f(n,x+2)...f(n,x+6)有关因而，遍历f(n−1) 中各点数和的概率，并将其相加至 f(n)中所有相关项，
  即可完成 f(n−1) 至 f(n) 的递推。
 *
 */
public class DicesProbability {

    public double[] dicesProbability(int n) {
        if (n < 1) return new double[0];
        double[] dp = new double[6];
        Arrays.fill(dp,1.0/6.0);
        for (int i = 2; i <=n ; i++) {
            double[] tmp = new double[5*i+1];
            //f(n-1,x)->f(n,x+1),f(n,x+2)...f(n,x+6)
            for (int j = 0; j < dp.length; j++) {
                for (int k = 0; k < 6; k++) {
                    tmp[j+k] += dp[j]/6.0;
                }
            }
            dp=tmp;
        }
        return dp;
    }


    public static void main(String[] args) {
        DicesProbability Main = new DicesProbability();
        System.out.println(Arrays.toString(Main.dicesProbability(2)));
    }
}
